#include<iostream>
using namespace std;
#define N 5
int maze[N][N]={
	{0,1,0,0,0},
	{0,1,0,1,0},
	{0,0,0,0,0},
	{0,1,1,1,0},
	{0,0,0,1,0}
};
int direction[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int visited[N][N]={0};
void printPath(int path[N][N],int length){
	for(int i=0;i<length;i++){
		for(int j=0;j<length;j++){
			cout <<path[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
}
int dfs(int x,int y,int path[N][N]){
	if(x==N-1 && y==N-1){
		path[x][y]=9;
		printPath(path,N);
		return 1;
	}
	visited[x][y]=3;
	path[x][y]=6;
	for(int i=0;i<4;i++){
		int newX=x+direction[i][0];
		int newY=y+direction[i][1];
		if(newX>=0 && newX<N && newY>=0 && newY<N && maze[newX][newY]==0 && !visited[newX][newY]){
			if(dfs(newX,newY,path)){
				return 1;
			}
		}
	}
	path[x][y]=0;
	return 0;
}


int main(){
	int path[N][N]={0};
	if(!dfs(0,0,path)){
		cout<<"No path found!"<<endl;
	}
}
